1. Field of the Invention
This application relates to the field of computer operating systems and more particularly to the field of multitasking-based operating systems that may be used on a microprocessor.
2. Description of Related Art
Operating systems may be used to facilitate sharing of a processor among a variety of separate processes. The operating system manages the sharing of the processor by providing each process with separate time slices for executing code.
For microprocessors, and for microprocessors used in device oriented applications, such as for data communication, it is often useful to provide an operating system that can manage processor sharing among the processes that handle different aspects of running the device. However, such operating systems may provide a number of drawbacks, such as requiring a significant amount of stack space that needs to be managed for each separate process. In addition, different mechanisms may be used for preempted task swapping (i.e., task swapping that uses interrupts) versus cooperative task swapping (i.e., processes relinquish the processor voluntarily). Furthermore, many operating systems are hardware and architecture specific so that an operating system implemented on one processor may not be easily be ported to another processor.
In addition, even in instances where it would be advantageous to use multiple process schedulers, many operating systems use a single process scheduler because of difficulties associated with changing process schedulers during run time. Context swapping in these operating systems may be cumbersome and, when both cooperative and preemptive techniques are used together, it may be difficult to avoid process starvation of a current process that is swapped in when a previous process voluntarily relinquishes the processor and the current process is subsequently preempted.
It is desirable to provide an operating system that overcomes the deficiencies discussed above.
According to the present invention, inhibiting process starvation in a multitasking operating system includes providing a first type of scheduling event at periodic timer intervals, providing a second type of second scheduling event in response to a running processes voluntarily relinquishing the processor, and, in response to a scheduling event, replacing an old process with a new process only if the old process has run for more than a predetermined amount of time. The predetermined amount of time may be one half of the timer interval. Further included may be determining if the old process has run for more than a predetermined amount of time by using clock slice checking. Further included may be determining if the old process is running in response to a second type of scheduling event and setting a flag in response thereto. Further included may be determining if the old process has run for more than a predetermined amount of time by checking the state of the flag. Further included may be, if the flag has been set, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. Further included may be, if the flag has been set and the old process has run for less than the predetermined amount of time, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. Further included may be determining if the old process is running in response to a second type of scheduling event and if the old process has run for less than the predetermined amount of time and setting a flag in response thereto. Further included may be determining if the old process has run for more than a predetermined amount of time by checking the state of the flag. Further included may be, if the flag has been set, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. The predetermined amount of time may be one half of a timer interval.
The system described herein provides a small kernel that can run on a variety of hardware platforms, such as a PowerPC based Symmetrix adapter board used in a Symmetrix data storage device provided by EMC Corporation of Hopkinton, Mass. The core kernel code may be written for the general target platform, such as the PowerPC architecture. Since the PowerPC implementation specific modules are well defined, the system may be quite portable between PowerPC processors (such as the 8260 and 750), and should prove relatively easy to port to any PowerPC based Symmetrix adapter board/CPU combination. The kernel may also be ported to run on other RISC machines (Hitachi SH series) and can be ported to CISC architectures.
The system described herein may be implemented using approximately 8000 lines of commented source code and approximately 1200 lines of assembly code (e.g., PowerPC assembly code) that may be used for a vector table and context swapping routines. The rest of the source code may be written in a higher-level language, such as C. The system core kernel may include a context swapping model, a process and threading model, a locking and process synchronization model, a simple scheduler, base system calls, and a basic device driver model.
The system described herein does not necessarily require specific device drivers, specific boot up or processor initialization code, a specific memory management model (for example, sbrk, malloc and free), specific networking code, and/or specific applications, although some of these functions may be useful for the system. Since the system is meant to function as an embedded operating system rather than as a general purpose base platform, everything not directly connected to essential kernel services may be designed for each implementation. For example, even if inter-process communications were not part of the core kernel, a very rich set of signals, semaphores and process synchronization functions may be provided as part of the core kernel to allow virtually any model of inter-process communication to be incorporated.
The system may be built using the Cygnus GnuPRO tool. The Cygnus GnuPRO libraries (e.g., the multi-threaded libc) may be used to provide basic routines such as string functions, etc. The kernel may use standard calling conventions based on traditional Unix API calls (open, close, read, write, ioctl, etc.) and traditional Unix libc system calls (printf, strcpy, atoi, etc.). There are some calls that may be specific to the system described herein.
The system described herein is fully 32-bit, pre-emptive and/or cooperative, multi-threaded, and multi-tasking. However, the system may run in a single address space. In some embodiments, there is no definable xe2x80x9cuserxe2x80x9d or xe2x80x9ckernelxe2x80x9d memory space enforced by the operating system. In addition, in some embodiments, the kernel memory areas may be statically defined, thus reducing the need for dynamic memory allocation. However, although there may be no kernel support for such routines as sbrk( ), malloc( ) and free( ), any task thread may employ analogous functions as desired. For example, a TCP/IP stack application can manage its own buffer space, and provide callable functions for buffer management.
In order to run on many different types of hardware, the system described herein supports a very simple and powerful organization that includes CPU initialization and boot code, a CPU vector table, a context swapping model, a scheduler interrupt service routine, a process/threading model, critical regions (non-preemptable areas), a scheduler, a simple locking mechanism, process synchronization, a device driver model, system calls, and general API""s. Some of these items may be hardware specific, but comprise a very small portion of the kernel. The modules for these items may be written in assembly language. The rest of the items may all be written in a high level language, such as C. With the exception of the context block information held for each process, the routines may be non-hardware specific, thus greatly enhancing kernel portability.
The system described herein exhibits many benefits. For example, processes need not carry around enough stack space to support a context swap, since context swaps may be made using very little, if any, stack space. When there are many processes, the amount of memory saved may be considerable. In addition, since the maximum number of interrupts that can be stacked may be generally well-known at compile time, the number of nested contexts may be known, and thus the maximum number of context blocks may be determined and may be statically allocated. The use of statically allocated context blocks and stack blocks may greatly enhance the debugging process because each process""s stack frame may be isolated, along with the process state and therefore it is not necessary to xe2x80x9cguessxe2x80x9d which parts of a system stack frame belong to which process. The kernel itself does not need a stack of its own. Parts of the kernel may use their own small stacks, such as the scheduler which runs as a pseudo-process (but also could run as a process in other embodiments), but there is no requirement for a special xe2x80x9csystem onlyxe2x80x9d stack. All interrupt service routines may start with interrupts disabled. Thus, the decision of whether to re-enable interrupts may be deferred to run-time, provided that the maximum number of nested contexts is not exceeded.
Interrupt services may be designed such that there is a very small ISR that runs when the interrupt is taken, with the bulk of the functionality being deferred to a process. Under this scheme, the role of the ISR may be to flag process(es) that it should run. Since processes may run with interrupts enabled (under most circumstances), this allows the scheduling algorithm and processes to be the major factors determining system responsiveness, rather than ISR processing and context swapping time.